package com.zdp.algorithm.stackandqueue;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;

/**
 * 获取窗口内的最大值
 * @author Zhengdp
 * @date 2023年01月08日 14:42
 */
@Slf4j
public class MaxWindow {
    public static void main(String[] args) {
        MaxWindowImpl maxWindow = new MaxWindowImpl();
        int[] arr = new int[]{
                4,3,5,4,3,3,6,7
        };
        int[] result = maxWindow.getMaxWinodw(arr, 3);
        for(int e :result){
            log.info("{}",e);
        }
    }
}

/**
 * 使用单调队列即可
 * 队列中的元素，保证单调递减 && 元素的顺序与原队列相同
 */
class MaxWindowImpl {
    /**
     * 获取窗口内的最大值数组
     * @param arr 原队列
     * @param w 窗口大小
     * @return 最大值数组
     */
    public int[] getMaxWinodw(int[] arr , int w){
        List<Integer> maxWindow  = new ArrayList<>();
        int[] result = new int[arr.length - w +1];
        int resultIndex = 0;
        // 初始化数组
        for(int i = 0; i < w;i++){
            if(maxWindow.size() == 0){
                maxWindow.add(arr[i]);
            }else {
                addMaxNum(maxWindow,arr[i]);
            }
        }
        // 滑动数组
        int left = 0,right = w;
        for(;right < arr.length ; right ++){
            result[resultIndex++] = maxWindow.get(0);
            int addNum = arr[right];
            int moveNum = arr[left ++];
            if(moveNum == maxWindow.get(0)){
                maxWindow.remove(0);
            }
            addMaxNum(maxWindow,addNum);
        }
        result[resultIndex++] = maxWindow.get(0);
        return result;
    }

    private void addMaxNum(List<Integer> maxWindow,int addNum){
        while(maxWindow.size() != 0 && maxWindow.get(maxWindow.size() -1) < addNum) {
            maxWindow.remove(maxWindow.size() - 1);
        }
        maxWindow.add(addNum);
    }
}
